package com.atguigu.structures.tree.node;

/**
 * 树节点
 *
 * @author xr-8
 * @date 2022-09-21
 * @time 23:31
 */
public class TreeNode {
    private int id;
    private String name;
    private TreeNode left;
    private TreeNode right;

    // 线索化二叉树时判断是否存在前驱节点
    private int leftType;
    // 线索化二叉树时判断是否存在后继节点
    private int rightType;

    /**
     * 前序遍历
     */
    public void preOrder() {
        System.out.println(this.id);
        if (this.left != null) {
            this.left.preOrder();
        }
        if (this.right != null) {
            this.right.preOrder();
        }
    }
    /**
     * 中序遍历
     */
    public void infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }
        System.out.println(this.id);
        if (this.right != null) {
            this.right.infixOrder();
        }
    }
    /**
     * 后序遍历
     */
    public void postOrder() {
        if (this.left != null) {
            this.left.postOrder();
        }
        if (this.right != null) {
            this.right.postOrder();
        }
        System.out.println(this.id);
    }

    /**
     * 前序遍历查找
     * @param no
     * @return
     */
    public TreeNode preOrderSearch(int no) {
        System.out.println("preOrderSearch");
        if (this.id == no) {
            return this;
        }
        //1.则判断当前结点的左子节点是否为空，如果不为空，则递归前序查找
        //2.如果左递归前序查找，找到结点，则返回
        TreeNode result = null;
        if (this.left != null) {
            result = this.left.preOrderSearch(no);
        }
        if (result != null) {//说明我们左子树找到
            return result;
        }
        //1.左递归前序查找，找到结点，则返回，否继续判断，
        //2.当前的结点的右子节点是否为空，如果不空，则继续向右递归前序查找
        if (this.right != null) {
            result = this.right.preOrderSearch(no);
        }
        return result;
    }
    /**
     * 中序遍历查找
     * @param no
     * @return
     */
    public TreeNode infixOrderSearch(int no) {
        TreeNode result = null;
        //判断当前结点的左子节点是否为空，如果不为空，则递归中序查找
        if (this.left != null) {
            result = this.left.infixOrderSearch(no);
        }
        //如果左子树找到，则返回，
        if (result != null) {
            return result;
        }
        System.out.println("infixOrderSearch");
        //如果左子树没有找到，就和当前结点比较，如果是则返回当前结点
        if (this.id == no) {
            return this;
        }
        //否则继续进行右递归的中序查找
        if (this.right != null) {
            result = this.right.infixOrderSearch(no);
        }
        return result;
    }
    /**
     * 后序遍历查找
     * @param no
     * @return
     */
    public TreeNode postOrderSearch(int no) {
        TreeNode result = null;
        //判断当前结点的左子节点是否为空，如果不为空，则递归后序查找
        if (this.left != null) {
            result = this.left.postOrderSearch(no);
        }
        if (result != null) {//说明在左子树找到
            return result;
        }
        //如果左子树没有找到，则向右子树递归进行后序遍历查找
        if (this.right != null) {
            result = this.right.postOrderSearch(no);
        }
        if (result != null) {//说明在右子树找到
            return result;
        }
        System.out.println("postOrderSearch");
        //如果左右子树都没有找到，就比较当前结点是不是
        if (this.id == no) {
            return this;
        }
        return result;
    }

    /**
     * 删除节点
     * 1)如果删除的节点是叶子节点，则删除该节点
     * 2)如果删除的节点是非叶子节点，则删除该子树
     * @param no
     */
    public void delNode(int no) {
        // 1、如果当前结点的左子结点不为空，并且左子结点就是要删除结点，就将this.left=null;并且就返回(结束递归删除)；
        if (this.left != null && this.left.getId() == no) {
            System.out.println("删除成功~");
            this.left = null;
            return;
        }
        // 2、如果当前结点的右子结点不为空，并且右子结点就是要删除结点，就将this.right=null;并且就返回(结束递归删除)；
        if (this.right != null && this.right.getId() == no) {
            System.out.println("删除成功~~");
            this.right = null;
            return;
        }
        // 3、如果第2和第3步没有删除结点，那么我们就需要向左子树进行递归删除；
        if (this.left != null ) {
            this.left.delNode(no);
        }
        // 4、如果第4步也没有删除结点，则应当向右子树进行递归删除。
        if (this.right != null) {
            this.right.delNode(no);
        }
    }

    public TreeNode(int id, String name) {
        this.id = id;
        this.name = name;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public TreeNode getLeft() {
        return left;
    }

    public void setLeft(TreeNode left) {
        this.left = left;
    }

    public TreeNode getRight() {
        return right;
    }

    public void setRight(TreeNode right) {
        this.right = right;
    }

    public int getLeftType() {
        return leftType;
    }

    public void setLeftType(int leftType) {
        this.leftType = leftType;
    }

    public int getRightType() {
        return rightType;
    }

    public void setRightType(int rightType) {
        this.rightType = rightType;
    }

    @Override
    public String toString() {
        return "HeroNode [id=" + id + ", name=" + name + ", leftType=" + leftType + ", rightType=" + rightType +
                ", leftNode=" + (left == null ? "null" : left.getId()) + ", rightNode=" + (right == null ? "null" : right.getId()) + "]";
    }

}
